# coding= utf-8
"""
最长公共子序列查找

解决LCS问题，需要把原问题分解成若干个子问题，所以需要刻画LCS的特征。

       设A=“a0，a1，…，am”，B=“b0，b1，…，bn”，且Z=“z0，z1，…，zk”为它们的最长公共子序列。不难证明有以下性质：
       如果am=bn，则zk=am=bn，且“z0，z1，…，z(k-1)”是“a0，a1，…，a(m-1)”和“b0，b1，…，b(n-1)”的一个最长公共子序列；
       如果am!=bn，则若zk!=am，蕴涵“z0，z1，…，zk”是“a0，a1，…，a(m-1)”和“b0，b1，…，bn”的一个最长公共子序列；
       如果am!=bn，则若zk!=bn，蕴涵“z0，z1，…，zk”是“a0，a1，…，am”和“b0，b1，…，b(n-1)”的一个最长公共子序列。
"""
# t[i][j]存储lcs(a[0,i]与b[0,i])，则t[m][n]存储的是目标lcs
t = [[-1 for clo in range(1000)] for row in range(1000)]


def lcs(a: str, b: str, ai, bi):
    if ai < 0 or bi < 0:
        t[ai][bi] = 0
    else:
        if a[ai] == b[bi]:
            res = lcs(a, b, ai - 1, bi - 1) + 1
        else:
            res = max(lcs(a, b, ai - 1, bi), lcs(a, b, ai, bi - 1))
        if res > t[ai][bi] or t[ai][bi] == -1:
            t[ai][bi] = res
    return t[ai][bi]


"""
也可以从反向来刻画特征：
    如果a[0]=b[0],则z[0=a[0]=b[0],且z[1,k]为a[1,m]和b[1,n]的lcs；
        如果a[0]!=b[0],且z[0]!=a[0],lcs存在于a[1,m]和b[0,n]的lcs中
        如果a[0]!=b[0],且z[0]!=b[0],lcs存在于a[0,m]和b[1,n]的lcs中，
    即如果a0!=b0,lcs为上面两种情况的最长的一个
"""
# 创建一个1000*1000的二维数组,存储a[i,m]与b[i,n]的lcs的长度
tab = []


def init_tab():
    global tab
    tab = [[-1 for clo in range(1000)] for row in range(1000)]


# 此方式从字符串头开始分解子问题，一步一步向后移动来拆解，直到一方为空串
# 返回值为lcs的长度，不是子序列
def __lcs(a: str, b: str, ai=0, bi=0) -> int:
    """
    目标string是a[ai:],b[bi:]
    """
    # 如果其中一个是空串，lcs为0
    if ai == len(a) or bi == len(b):
        tab[ai][bi] = 0
    elif tab[ai][bi] == -1:
        # 如果首字符相同
        if a[ai] == b[bi]:
            res = __lcs(a, b, ai + 1, bi + 1) + 1
        else:
            # 如果首字符不同
            res = max(__lcs(a, b, ai, bi + 1), __lcs(a, b, ai + 1, bi))
        if tab[ai][bi] == -1 or tab[ai][bi] < res:
            tab[ai][bi] = res
    return tab[ai][bi]


def getLcs(a: str, b: str):
    init_tab()
    lcs = __lcs(a, b)
    print(get(tab, a, b, len(a), len(b)))
    return lcs


def get(c, xs, ys, i, j):
    """
    表格的右下方开始。如果X和Y中最后一个元素相等，我们就把它作为结果中的最后一个元素，并沿
    着对角线方向继续查表。否则，如果最后一个元素不等，我们需要比较左侧和
    上方的项，选择值较大的继续进行处理。
    """
    if i == 0 or j == 0:
        return []
    elif xs[i - 1] == ys[j - 1]:
        return get(c, xs, ys, i - 1, j - 1) + [xs[i - 1]]
    elif c[i - 1][j] > c[i][j - 1]:
        return get(c, xs, ys, i - 1, j)
    else:  # 把相等的情况分在一个里面
        return get(c, xs, ys, i, j - 1)


def bottom2top(a: str, b: str) -> int:
    m = len(a)
    n = len(b)
    c = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return c[m][n]


# print(lcs('123', '132'))
a = '13456778'
b = '357486782'
# print(getLcs(a, b))
# print(bottom2top(a, b))
print(lcs(a, b, len(a) - 1, len(b) - 1))
